package lc4

/*
 * @lc app=leetcode.cn id=4 lang=golang
 *
 * [4] 寻找两个正序数组的中位数
 */
// 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数
// nums1.length == m
// nums2.length == n
// 0 <= m <= 1000
// 0 <= n <= 1000
// 1 <= m + n <= 2000
// -10^6 <= nums1[i], nums2[i] <= 10^6
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	if len(nums1) == 0 {
		return findMedianSortedArray(nums2)
	} else if len(nums2) == 0 {
		return findMedianSortedArray(nums1)
	}
	// 二分法粗劣查找中位数
	var (
		beg1Index     int
		lastBeg1Index int = beg1Index
		end1Index     int = len(nums1) - 1
		beg2Index     int
		lastBeg2Index int = beg2Index
		end2Index     int = len(nums2) - 1
	)
	for {
		index1 := findMedianIndexSortedArray(nums1, beg1Index, end1Index)
		index2 := findMedianIndexSortedArray(nums2, beg2Index, end2Index)
		if nums1[index1] < nums2[index2] {
			beg1Index = index1
			end2Index = index2
		} else if nums1[index1] > nums2[index2] {
			end1Index = index1
			beg2Index = index2
		}
		if lastBeg1Index == beg1Index || lastBeg2Index == beg2Index || index1 == index2 {
			break
		}
		lastBeg1Index = beg1Index
		lastBeg2Index = beg2Index
	}
	// 计算精确位置
	return findMedian(nums1, nums2, beg1Index, beg2Index)
}

// findMedianSortedArray 一个有序列表的中位数查找
func findMedianSortedArray(nums []int) float64 {
	if len(nums) == 0 {
		return 0
	} else if len(nums)%2 == 1 {
		return float64(nums[len(nums)/2])
	}
	return float64(nums[(len(nums)-1)/2]+nums[len(nums)/2]) / 2
}

// findMedianIndexSortedArray 返回中间值的索引，奇数取中间，偶数取中间前边一位
func findMedianIndexSortedArray(nums []int, begIndex, endIndex int) int {
	return (endIndex-begIndex)/2 + begIndex
}

func findMedian(nums1, nums2 []int, index1, index2 int) float64 {
	valFirst := nums1[index1]
	valSecond := nums2[index2]
	mid := (len(nums1) + len(nums2) - 1) / 2
	// 查找精确中位数，后移查找
	for index1+index2 < mid {
		if index1+1 < len(nums1) && index2+1 < len(nums2) {
			valFirst = max(nums1[index1], nums2[index2]) // 去掉最小值
			// 去掉最大值
			if nums1[index1+1] < nums2[index2+1] {
				index1++
				valSecond = nums1[index1]
			} else {
				index2++
				valSecond = nums2[index2]
			}
		} else if (index1 + 1) == len(nums1) {
			index2 = mid - index1
			valFirst, valSecond = nums1[index1], nums2[index2]
			break
		} else if (index2 + 1) == len(nums2) {
			index1 = mid - index2
			valFirst, valSecond = nums1[index1], nums2[index2]
			break
		}
	}
	// 查找精确中位数，迁移查找
	for index1+index2 > mid {
		if index1-1 >= 0 && index2-1 >= 0 {
			valFirst = min(nums1[index1], nums2[index2]) // 去掉最大值
			// 去掉最小值
			if nums1[index1-1] < nums2[index2-1] {
				index2--
				valSecond = nums2[index2]
			} else {
				index1--
				valSecond = nums1[index1]
			}
		} else if (index1 - 1) < 0 {
			index2 = mid - index1
			valFirst, valSecond = nums1[index1], nums2[index2]
			break
		} else if (index2 - 1) < 0 {
			index1 = mid - index2
			valFirst, valSecond = nums1[index1], nums2[index2]
			break
		}
		continue
	}
	// 校验较小值
	if index1-1 >= 0 || index2-1 >= 0 {
		minFix := minFix(nums1, index1, nums2, index2)
		if minFix > min(valFirst, valSecond) {
			valFirst = max(minFix, valFirst)
			valSecond = max(minFix, valSecond)
		}
	}
	// 校验较大值
	if index1+1 < len(nums1) || index2+1 < len(nums2) {
		maxFix := maxFix(nums1, index1, nums2, index2)
		if maxFix < max(valFirst, valSecond) {
			valFirst = min(maxFix, valFirst)
			valSecond = min(maxFix, valSecond)
		}
	}

	// 计算中位数
	if (len(nums1)+len(nums2))%2 == 1 {
		return float64(min(valFirst, valSecond))
	}
	return float64(valFirst+valSecond) / 2
}

func minFix(num1 []int, index1 int, num2 []int, index2 int) int {
	if index1 == 0 {
		return num2[index2-1]
	} else if index2 == 0 {
		return num1[index1-1]
	}
	return max(num1[index1-1], num2[index2-1])
}

func maxFix(num1 []int, index1 int, num2 []int, index2 int) int {
	if index1+1 == len(num1) {
		return num2[index2+1]
	} else if index2+1 == len(num2) {
		return num1[index1+1]
	}
	return min(num1[index1+1], num2[index2+1])
}

func min(a, b int) int {
	if a >= b {
		return b
	}
	return a
}

func max(a, b int) int {
	if a >= b {
		return a
	}
	return b
}
